package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 希尔排序(对插入排序的一种优化)
 *
 * @author WangJX
 * @version 1.0
 * @date 2019/11/3 11:04
 */
public class ShellSort {
    public static void main(String[] args) {
//        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};


//        创建一个80000的随机数组
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int)(Math.random() * 8000000);
        }

        //查看排序使用的时间
        Date d1 = new Date();
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println(sdf.format(d1));


        //shellSort(arr);
        shellSort2(arr);


        Date d2 = new Date();
        System.out.println(sdf.format(d2));


//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序 ----- 交换法
     *
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int tmp = 0;
        //判断要循环几次
        for (int i = arr.length / 2; i > 0; i /= 2) {
            //判断要分多少个组别
            for (int j = i; j < arr.length; j++) {
                //循环每组所对应要比较的数据,有几个组就隔开几个数据进行比较
                for (int k = j - i; k >= 0; k -= i) {
                    if (arr[k] > arr[k + i]) {
                        tmp = arr[k];
                        arr[k] = arr[k + i];
                        arr[k + i] = tmp;
                    }
                }
            }
        }
    }


    /**
     * 希尔排序 ------ 移位法,效率更快点
     *
     * @param arr
     */
    public static void shellSort2(int[] arr) {

        int a = 0;
        int tmp = 0;
        //判断要循环几次
        for (int i = arr.length / 2; i > 0; i /= 2) {
            //判断数据相隔的步距
            for (int j = i; j < arr.length; j++) {
                a = j;
                tmp = arr[j];
                //首次判断当前值是否比前一位的值大
                if (arr[a] < arr[a - i]) {
                    //循环判断找所取数据应该在当前组的具体位置
                    while (a - i >= 0 && tmp < arr[a - i]) {
                        arr[a] = arr[a - i];
                        a -= i;
                    }
                    //交换
                    arr[a] = tmp;
                }
            }
        }
    }
}
